{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Two Furthest Houses With Different Colors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两栋颜色不同且距离最远的房子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>街上有 <code>n</code> 栋房子整齐地排成一列，每栋房子都粉刷上了漂亮的颜色。给你一个下标从 <strong>0</strong> 开始且长度为 <code>n</code> 的整数数组 <code>colors</code> ，其中 <code>colors[i]</code> 表示第&nbsp; <code>i</code> 栋房子的颜色。</p>\n",
    "\n",
    "<p>返回 <strong>两栋</strong> 颜色 <strong>不同</strong> 房子之间的 <strong>最大</strong> 距离。</p>\n",
    "\n",
    "<p>第 <code>i</code> 栋房子和第 <code>j</code> 栋房子之间的距离是 <code>abs(i - j)</code> ，其中 <code>abs(x)</code> 是 <code>x</code> 的绝对值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/31/eg1.png\" style=\"width: 610px; height: 84px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>colors = [<strong><em>1</em></strong>,1,1,<em><strong>6</strong></em>,1,1,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>上图中，颜色 1 标识成蓝色，颜色 6 标识成红色。\n",
    "两栋颜色不同且距离最远的房子是房子 0 和房子 3 。\n",
    "房子 0 的颜色是颜色 1 ，房子 3 的颜色是颜色 6 。两栋房子之间的距离是 abs(0 - 3) = 3 。\n",
    "注意，房子 3 和房子 6 也可以产生最佳答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/31/eg2.png\" style=\"width: 426px; height: 84px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>colors = [<em><strong>1</strong></em>,8,3,8,<em><strong>3</strong></em>]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>上图中，颜色 1 标识成蓝色，颜色 8 标识成黄色，颜色 3 标识成绿色。\n",
    "两栋颜色不同且距离最远的房子是房子 0 和房子 4 。\n",
    "房子 0 的颜色是颜色 1 ，房子 4 的颜色是颜色 3 。两栋房子之间的距离是 abs(0 - 4) = 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>colors = [<em><strong>0</strong></em>,<em><strong>1</strong></em>]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>两栋颜色不同且距离最远的房子是房子 0 和房子 1 。\n",
    "房子 0 的颜色是颜色 0 ，房子 1 的颜色是颜色 1 。两栋房子之间的距离是 abs(0 - 1) = 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n ==&nbsp;colors.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= colors[i] &lt;= 100</code></li>\n",
    "\t<li>生成的测试数据满足 <strong>至少 </strong>存在 2 栋颜色不同的房子</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [two-furthest-houses-with-different-colors](https://leetcode.cn/problems/two-furthest-houses-with-different-colors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [two-furthest-houses-with-different-colors](https://leetcode.cn/problems/two-furthest-houses-with-different-colors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,6,1,1,1]', '[1,8,3,8,3]', '[0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if colors[j] != colors[i]:\n",
    "                    res = max(res, abs(i - j))\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        res = 0\n",
    "        # for i in range(len(colors)):\n",
    "        #     for j in range(i,len(colors)):\n",
    "        #         if colors[i] != colors[j]:\n",
    "        #             res = max(res,abs(i-j))\n",
    "        # return res\n",
    "        for i in range(1,len(colors)):\n",
    "            if colors[i] != colors[0]:\n",
    "                res = max(res,i)\n",
    "            if colors[len(colors)-i-1] != colors[len(colors)-1]:\n",
    "                res = max(res,i)\n",
    "        # for j in range(len(colors)-2,-1,-1):\n",
    "        #     if colors[j] != colors[-1]:\n",
    "        #         res = max(res,abs(j-len(colors)+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        start = colors[0]\n",
    "        n = len(colors)\n",
    "        for i in range(n):\n",
    "            if colors[i] != start or colors[-1-i] != start:\n",
    "                return max(i, n-i-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n, ans = len(colors), 0\n",
    "        for l in range(n - 1):\n",
    "            for r in range(n - 1, l, -1):\n",
    "                if r - l < ans: break\n",
    "                if colors[l] != colors[r]: \n",
    "                    ans = r - l\n",
    "                    break\n",
    "            if n - l < ans: break\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        start = colors[0]\n",
    "        n = len(colors)\n",
    "        for i in range(n):\n",
    "            if colors[i] != start or colors[-1-i] != start:\n",
    "                return max(i, n-i-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n=len(colors)\n",
    "        j=n-1\n",
    "        for k in range(j,0,-1):\n",
    "            if colors[k]!=colors[0]:\n",
    "                r=k\n",
    "                break\n",
    "        for k in range(j):\n",
    "            if colors[k]!=colors[j]:\n",
    "                l=j-k\n",
    "                break\n",
    "        return max(l,r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        if colors[0] != colors[-1]:\n",
    "            return n-1\n",
    "        else:\n",
    "            l, r = 0, n-1\n",
    "            while l < n and colors[l] == colors[-1]:\n",
    "                l += 1\n",
    "            while r >= 0 and colors[r] == colors[0]:\n",
    "                r -= 1\n",
    "            return max(r, n-l-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        i, j = 0, n-1\n",
    "\n",
    "        while i < n:\n",
    "            if colors[i] == colors[n - 1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        while j >= 0:\n",
    "            if colors[j] == colors[0]:\n",
    "                j -= 1\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        return max(j, n - i - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        if colors[0] != colors[-1]:\n",
    "            return len(colors)-1\n",
    "        left, right= 0, len(colors)-1\n",
    "        while colors[0] == colors[left]:\n",
    "            left += 1\n",
    "        while colors[-1] == colors[right]:\n",
    "            right -= 1\n",
    "        return max(len(colors)-left-1, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        cur = 0\n",
    "        for i, item in enumerate(colors):\n",
    "            for j in range(len(colors)-1, i, -1):\n",
    "                if item != colors[j]:\n",
    "                    cur = max(cur, j-i)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "\n",
    "        slow, fast = 0, 1\n",
    "        result = 0\n",
    "\n",
    "        while slow < len(colors):\n",
    "            while fast < len(colors):\n",
    "                if colors[fast] != colors[slow]:\n",
    "                    result = max(fast-slow, result)\n",
    "                fast += 1\n",
    "            slow += 1\n",
    "            fast = slow + 1\n",
    "            if len(colors) - slow <= result:\n",
    "                return result\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(colors)):\n",
    "            for j in range(i,len(colors)):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res,abs(i-j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        i, j = 0, len(colors) - 1\n",
    "        a, b = 0, 0\n",
    "        while i <= j:\n",
    "            if colors[i] != colors[j]:\n",
    "                a = j - i\n",
    "                break\n",
    "            else:\n",
    "                j -= 1\n",
    "        i, j = 0, len(colors) - 1\n",
    "        while i <= j:\n",
    "            if colors[i] != colors[j]:\n",
    "                b = j - i\n",
    "                break\n",
    "            else:\n",
    "                i += 1\n",
    "        return max(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        st = set(colors)\n",
    "        left = dict()\n",
    "        right = dict()\n",
    "\n",
    "        for c in st:\n",
    "            left[c] = -1\n",
    "            right[c] = -1\n",
    "        \n",
    "        cnt = 0\n",
    "        for idx, c0 in enumerate(colors):\n",
    "            for c1 in st:\n",
    "                if c0 != c1 and left[c1] == -1:\n",
    "                    left[c1] = idx\n",
    "                    cnt += 1\n",
    "            if cnt == len(st):\n",
    "                break\n",
    "\n",
    "        n = len(colors)\n",
    "        cnt = 0\n",
    "        for idx, c0 in enumerate(colors[::-1]):\n",
    "            for c1 in st:\n",
    "                if c0 != c1 and right[c1] == -1:\n",
    "                    right[c1] = n - 1 - idx\n",
    "                    cnt += 1\n",
    "            if cnt == len(st):\n",
    "                break\n",
    "\n",
    "        ans = 0\n",
    "        for idx, c in enumerate(colors):\n",
    "            ans = max(ans, abs(idx - left[c]), abs(idx - right[c]))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        dist=0\n",
    "        for i in range(len(colors)):\n",
    "            for j in range(i+1,len(colors)):\n",
    "                if colors[i]!=colors[j]:\n",
    "                    dist=max(dist,abs(i-j))\n",
    "                    \n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        l = len(colors)\n",
    "        if colors[0] != colors[-1]:\n",
    "            return l-1\n",
    "        left, right   = 1 ,l - 2\n",
    "        while colors[left] == colors[0]:\n",
    "            left += 1\n",
    "        while colors[right] == colors[-1]:\n",
    "            right -= 1\n",
    "        return max(right,l-1-left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        res = 0   # 两栋颜色不同房子的最远距离\n",
    "        # 遍历两栋房子下标并维护最远距离\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res, j - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        left, right = 0, n - 1\n",
    "        while colors[-1] == colors[left]:\n",
    "            left += 1\n",
    "        while colors[0] == colors[right]:\n",
    "            right -= 1\n",
    "        return max(n - left - 1, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n=len(colors)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if colors[i]!=colors[j]:\n",
    "                    res = max(res,j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 一刷\n",
    "# class Solution:\n",
    "#     def maxDistance(self, colors: List[int]) -> int:\n",
    "#         res = 0\n",
    "#         n = len(colors)\n",
    "#         for i in range(n):\n",
    "#             for j in range(i,n):\n",
    "#                 if colors[i] != colors[j]:\n",
    "#                     res = max(res, j-i)\n",
    "#         return res\n",
    "\n",
    "# 二刷\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        left, right = 0, n - 1\n",
    "        while colors[-1] == colors[left]: \n",
    "            left += 1\n",
    "        while colors[0] == colors[right]: \n",
    "            right -= 1\n",
    "        return max(n - left - 1, right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxDistance(self, colors: List[int]) -> int:\r\n",
    "        n = len(colors)\r\n",
    "        \r\n",
    "        result = 0\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(i+1, n):\r\n",
    "                if colors[i] == colors[j]:\r\n",
    "                    continue\r\n",
    "                else:\r\n",
    "                    result = max(j-i, result)\r\n",
    "                    \r\n",
    "        return result\r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        x=0\n",
    "        l=len(colors)\n",
    "        for i in range(l):\n",
    "            for j in range(i,l):\n",
    "                 if colors[i]!=colors[j]:\n",
    "                     x=max(x,j-i)\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        x=0\n",
    "        y=len(colors)-1\n",
    "        if colors[x]!=colors[y]:\n",
    "            return y-x\n",
    "        else:\n",
    "            s=[]\n",
    "            while x<len(colors)-1:\n",
    "                if colors[x]!=colors[y]:\n",
    "                    s.append(abs(y-x))\n",
    "                x+=1\n",
    "            while y>0:\n",
    "                x=0\n",
    "                if colors[x]!=colors[y]:\n",
    "                    s.append(abs(y-x))\n",
    "                y-=1\n",
    "            return max(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        dis = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    dis = max(dis, j - i)\n",
    "        return dis\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in range(len(colors)):\n",
    "            for j in range(i):\n",
    "                if colors[i]!=colors[j]:\n",
    "                    res=max(res,i-j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        if colors[0] != colors[-1]:\n",
    "            return n - 1\n",
    "        col = colors[0]\n",
    "        distance = 0\n",
    "        for i in range(1,n - 1):\n",
    "            if colors[i] != col:\n",
    "                distance = max(distance,max(i, n - 1 - i))\n",
    "        \n",
    "        return distance\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors):\n",
    "        l = len(colors)\n",
    "        if colors[0]!=colors[l-1]:\n",
    "            return l-1\n",
    "        else:\n",
    "            res = 0\n",
    "            for i in range(1,l):\n",
    "                if colors[i]!=colors[0]:\n",
    "                    res = max(res,i)\n",
    "                if colors[i]!=colors[l-1]:\n",
    "                    res = max(res,l-i-1)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "\n",
    "        # left pointer < len(colors)\n",
    "        # right pointer < left pointer OR color different\n",
    "        # max_dis = integer\n",
    "\n",
    "        pointer1, pointer2 = 0, len(colors)-1\n",
    "        max_dis = 0\n",
    "\n",
    "        while pointer1 <= len(colors)/2:\n",
    "\n",
    "            if colors[pointer1] == colors[pointer2]:\n",
    "                pointer2 -= 1\n",
    "            \n",
    "            if colors[pointer1] != colors[pointer2]:\n",
    "                max_dis = max(pointer2 - pointer1, max_dis)\n",
    "                pointer2 = len(colors)-1\n",
    "                pointer1 += 1\n",
    "            \n",
    "        return max_dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if colors[i] != colors[0]:\n",
    "                m1 = i\n",
    "                break\n",
    "        #print(m1)\n",
    "        for i in range(0, n - 1):\n",
    "            if colors[i] != colors[n - 1]:\n",
    "                m2 = n - 1 - i\n",
    "                break\n",
    "        return max(m1, m2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        # ans=0\n",
    "        n=len(colors)\n",
    "        i,j=0,n-1\n",
    "        while colors[i]==colors[j]:\n",
    "            j-=1\n",
    "        l1=j-i \n",
    "        i,j=0,n-1\n",
    "        while colors[i]==colors[j]:\n",
    "            i+=1\n",
    "        l2=j-i \n",
    "        return max(l1,l2)\n",
    "            \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(colors) - 1):\n",
    "            for j in range(i + 1, len(colors)):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res, j - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        left, right = 0, n - 1\n",
    "        while colors[-1] == colors[left]: \n",
    "            left += 1\n",
    "        while colors[0] == colors[right]: \n",
    "            right -= 1\n",
    "        return max(n - left - 1, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i, x in enumerate(colors):\n",
    "            for j in range(len(colors) - 1, -1, -1):\n",
    "                if x != colors[j]:\n",
    "                    ans = max(ans, j - i)\n",
    "                if j - i <= ans:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        dis = 0\n",
    "        n = len(colors)\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,i+dis,-1):\n",
    "                if colors[i] != colors[j]:\n",
    "                    dis = max(dis,j-i)\n",
    "                    break\n",
    "        return dis\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(colors)):\n",
    "            for j in range(len(colors)):\n",
    "                if colors[j] != colors[i]:\n",
    "                    res = max(res,abs(j-i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        right = n - 1\n",
    "        left = 0\n",
    "        if colors[right] != colors[left]:\n",
    "            return right - left\n",
    "        while right >= 0:\n",
    "            if colors[right] != colors[right - 1]:\n",
    "                break \n",
    "            right -= 1\n",
    "        while left < n - 1:\n",
    "            if colors[left] != colors[left + 1]:\n",
    "                break\n",
    "            left += 1\n",
    "        return max(n-1 - left  - 1, right  - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        res = 0   # 两栋颜色不同房子的最远距离\n",
    "        # 遍历两栋房子下标并维护最远距离\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res, j - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res,j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    if j-i > ans:\n",
    "                        ans = j-i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        l = 0\n",
    "        n = len(colors)\n",
    "        a = None\n",
    "        b = None\n",
    "        while l < n:\n",
    "            if colors[l] != colors[-1]:\n",
    "                a = n - 1 - l\n",
    "                break\n",
    "            l += 1\n",
    "        r = n - 1\n",
    "        while r >= 0:\n",
    "            if colors[r] != colors[0]:\n",
    "                b = r\n",
    "                break\n",
    "            r -= 1\n",
    "        return max(a, b)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        #copy\n",
    "        n = len(colors)\n",
    "        res =0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res,j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i,n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res,j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        # 双指针\n",
    "        n = len(colors)\n",
    "        p, q = 0, n-1\n",
    "        ans = 0\n",
    "        while p < q:\n",
    "            if colors[p] != colors[q]:\n",
    "                ans = max(ans, q-p)\n",
    "                break\n",
    "            q -= 1\n",
    "        \n",
    "        p, q = 0, n-1\n",
    "        while p < q:\n",
    "            if colors[p] != colors[q]:\n",
    "                ans = max(ans, q-p)\n",
    "                break\n",
    "            p += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(colors)\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res, abs(i-j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        dic1 = collections.defaultdict(int)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "        for i, c in enumerate(colors):\n",
    "            if c not in dic1:\n",
    "                dic1[c] = i\n",
    "            else:\n",
    "                dic1[c] = min(i, dic1[c])\n",
    "            if c not in dic2:\n",
    "                dic2[c] = i\n",
    "            else:\n",
    "                dic2[c] = max(i, dic2[c])\n",
    "        res = float('-inf')\n",
    "        meet = set()\n",
    "        for k in dic1.keys():\n",
    "            if k in meet:continue\n",
    "            for t in dic1.keys():              \n",
    "                if k == t:continue\n",
    "                temp1 = abs(dic1[k] - dic2[t])\n",
    "                temp2 = abs(dic2[k] - dic1[t])\n",
    "                temp = max(temp1, temp2)\n",
    "                res = max(temp, res)\n",
    "            meet.add(k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(colors)-1):\n",
    "            for j in range(i+1,len(colors)):\n",
    "                if colors[i]!=colors[j]:\n",
    "                    ans=max(ans,j-i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        if colors[0] != colors[-1]:\n",
    "            return len(colors) - 1\n",
    "        n = len(colors)\n",
    "        max_dis = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if colors[j] != colors[i]:\n",
    "                    max_dis = max(max_dis, j - i)\n",
    "\n",
    "        return max_dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    ret = max(ret, j - i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        res = 0  # 两栋颜色不同房子的最远距离\n",
    "        # 遍历两栋房子下标并维护最远距离\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res, j - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        for i in reversed(range(len(colors)+1)):\n",
    "            for j in range(len(colors) - i):\n",
    "                if colors[j] != colors[j+i]:\n",
    "                    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        res = 0   # 两栋颜色不同房子的最远距离\n",
    "        # 遍历两栋房子下标并维护最远距离\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res, j - i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        left, right = 0, n - 1\n",
    "        while colors[-1] == colors[left]: \n",
    "            left += 1\n",
    "        while colors[0] == colors[right]: \n",
    "            right -= 1\n",
    "        return max(n - left - 1, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    ans = max(ans, j - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(colors)):\n",
    "            for j in range(i+1, len(colors)):\n",
    "                if colors[i] != colors[j]:\n",
    "                    res = max(res, j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        left, right = 0, len(colors)-1\n",
    "        lc, rc = colors[left], colors[right]\n",
    "        while True:\n",
    "            if lc != colors[right] or rc != colors[left]:\n",
    "                break\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return max(right, len(colors)-1-left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if colors[i] != colors[j]:\n",
    "                    ans = max(ans, j - i)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(colors) // 2):\n",
    "            distance = 0\n",
    "            startColor = colors[i]\n",
    "            for j in range(i + 1, len(colors)):\n",
    "                distance += 1\n",
    "                if colors[j] != startColor:\n",
    "                    res = max(res, distance)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        m = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + m, n):\n",
    "                if colors[i] != colors[j]:\n",
    "                    m = max(m, j - i)\n",
    "        return m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n = len(colors)\n",
    "        l = r = 0\n",
    "        while colors[l] == colors[-1]:\n",
    "            l += 1\n",
    "        while colors[~r] == colors[0]:\n",
    "            r += 1\n",
    "        return max(l, r, n-r-1, n-l-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        j = len(colors)-1\n",
    "        aa = len(colors)\n",
    "        while j>=0:\n",
    "            a = j\n",
    "            while a<aa:\n",
    "                if colors[a]!=colors[a-j]:\n",
    "                    return j\n",
    "                a+=1\n",
    "            j-=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(colors) -1\n",
    "        while colors[left] == colors[right] and left <= right:\n",
    "            left = left + 1\n",
    "        \n",
    "        temp = right - left\n",
    "        left = 0\n",
    "        right = len(colors) -1\n",
    "        while colors[left] == colors[right] and left <= right:\n",
    "            right = right - 1\n",
    "        \n",
    "        return max(temp, right - left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        p,q=0,len(colors)-1\n",
    "        while colors[p]==colors[q]:\n",
    "            p+=1\n",
    "        h1=q-p\n",
    "        p,q=0,len(colors)-1\n",
    "        while colors[p]==colors[q]:\n",
    "            q-=1   \n",
    "        h2=q-p\n",
    "        return max(h1,h2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        start = colors[0]\n",
    "        n = len(colors)\n",
    "        for i in range(n):\n",
    "            if colors[i] != start or colors[-1-i] != start:\n",
    "                return max(i, n-i-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "            max_result = 0\n",
    "            max_d = 0\n",
    "            n = len(colors)\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    if colors[i] != colors[j]:\n",
    "                        max_d = j - i\n",
    "                    if max_d > max_result:\n",
    "                        max_result = max_d\n",
    "            return max_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        p = 0\n",
    "        q = len(colors) - 1\n",
    "        l = colors[p]\n",
    "        r = colors[q]\n",
    "        while True:\n",
    "            if l != colors[q] or r != colors[p]:\n",
    "                break\n",
    "            else:\n",
    "                p += 1\n",
    "                q -= 1\n",
    "\n",
    "        return max(abs(0 - q), abs(len(colors) - 1 - p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, colors: List[int]) -> int:\n",
    "        n=len(colors)\n",
    "        distance=float(\"-inf\")\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if colors[i]!=colors[j]:\n",
    "                    distance=max(distance,j-i)\n",
    "        return distance\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
